package main.Q701_800;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Q711_720 {
    public static void main(String[] args) {
        System.out.println("Question711：");
        System.out.println("Question712：");
        System.out.println("Question713：乘积小于K的子数组");
        System.out.println("Question714：买卖股票的最佳时机含手续费");
        System.out.println("Question715：");
        System.out.println("Question716：");
        System.out.println("Question717：");
        System.out.println("Question718：最长重复子数组");
        System.out.println("Question719：");
        System.out.println("Question720：词典中最长的单词");
        String[] words=new String[]{"a", "banana", "app", "appl", "ap", "apply", "apple"};
        System.out.println(new Question720().longestWord(words));
    }
}

class Question713{
    public static int numSubarrayProductLessThanK(int[] nums, int k) {
        int count=0;
        for (int i=0;i<nums.length;i++){
            int multi=1;
            for (int j=i;j<nums.length;j++){
                multi*=nums[j];
                if (multi<k) count++;
                else break;
            }
        }
        return count;
    }
}

class Question714{
    public int maxProfit(int[] prices, int fee) {
        int length= prices.length;
        int[][] dp=new int[length][2];
        for (int i=0;i<length;i++){
            if (i==0) {
                dp[i][0]=0;//当天没有股票
                dp[i][1]=0-prices[i];//当天有股票
            }else {
                dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);//i-1天没有股票或者i-1天有股票i天卖了
                dp[i][1]=Math.max(dp[i-1][0]-prices[i],dp[i-1][1]);//i-1天没有股票今天买了或者i-1天有股票
            }
        }
        return dp[length-1][0];
    }
}

class Question718{
    public static int findLength(int[] nums1, int[] nums2) {//类同与求两字符串的最长公共子串问题
        int length1=nums1.length,length2=nums2.length,maxLength=0;
        int[][] dp=new int[length1][length2];
        for (int i=0;i<length1;i++){
            for (int j=0;j<length2;j++){
                if (nums1[i]==nums2[j]&&i-1>=0&&j-1>=0) dp[i][j]=dp[i-1][j-1]+1;//相等且存在左上
                else if (nums1[i]==nums2[j]&&(i-1<0||j-1<0)) dp[i][j]=1;//相等且不存在左上
                maxLength=Math.max(maxLength,dp[i][j]);
            }
        }
        return maxLength;
    }
}

class Question720{
    public String longestWord(String[] words) {
        Arrays.sort(words, (a, b) ->  {
            if (a.length() != b.length()) {
                return a.length() - b.length();
            } else {
                return b.compareTo(a);
            }
        });
        String longest = "";
        Set<String> candidates = new HashSet<>();
        candidates.add("");
        int n = words.length;
        for (int i = 0; i < n; i++) {
            String word = words[i];
            if (candidates.contains(word.substring(0, word.length() - 1))) {
                candidates.add(word);
                longest = word;
            }
        }
        return longest;
    }
}